# -*- encoding: utf-8 -*-

# Ajout du répertoire des bibliothèques au PATH
import sys
sys.path.append('./lib/')
import gv

# import des bibliothèques
from pygraph.classes.graph import graph
from pygraph.classes.digraph import digraph
import pygraph.algorithms.minmax as mm
import copy
from pygraph.readwrite.dot import write

# Some graphs to test with
GRAPH1 = (["Alice", "Bob", "Someone", "SomeoneElse"], [("Alice","Bob", 2), ("Alice", "Someone", 1), ("Alice", "SomeoneElse", 3), ("Bob", "SomeoneElse", 42)])
GRAPH2 = (['a','b','c','d','e'],[('a','b',12),('a','c',24),('a','d',42),('a','e',5),('b','c',7),('b','d',13),('b','e',3),('c','d',1),('c','e',40),('d','e',5)])
GRAPH3 = (['a','b','c','d','e','f'],[('a','b',12),('a','c',24),('a','d',42),('a','e',5),('a','f',2),('b','c',7),('b','d',13),('b','e',3),('b','f',23),('c','d',1),('c','e',40),('c','f',3),('d','e',54),('d','f',5),('e','f',32)])



def create_graph((vertex, edges), draw=False):
    """Créer un graphe à partir de la liste de sommets et de celles des aretes (tuple de longueur 3)"""
    
    network = graph()
    network.add_nodes(vertex)
    for edge in edges:
        network.add_edge(edge[0:2], wt = edge[2], label = edge[2])
    if draw:
        dot = write(network)
        gvv = gv.readstring(dot)
        gv.layout(gvv,'dot')
        gv.render(gvv,'png','network.png')
    return network

NETWORK = create_graph(E2,True)

def minimum_spanning_tree(orig_graph, draw = False):
    tree_dictionnary = mm.minimal_spanning_tree(orig_graph)
    tree = graph()
    tree.add_nodes(orig_graph.nodes())
    for node in tree_dictionnary:
        if tree_dictionnary[node] != None:
            tree.add_edge((node, tree_dictionnary[node]), wt = orig_graph.edge_weight((node, tree_dictionnary[node])), label = orig_graph.edge_weight((node, tree_dictionnary[node])))
    if draw:
        dot = write(tree)
        gvv = gv.readstring(dot)
        gv.layout(gvv,'dot')
        gv.render(gvv,'png','spanning_tree.png')
    return tree

ACM = minimum_spanning_tree(NETWORK, True)

def display_cool(acm, network):
    res = copy.deepcopy(network)
    e1 = res.edges()
    e2 = acm.edges()
    for i in e1:
        if (i in e2):
            print i
    #print network.edges()
    #dot = write(tree)
    #gvv = gv.readstring(dot)
    #gv.layout(gvv,'dot')
    #gv.render(gvv,'png','spanning_tree.png')

display_cool(ACM, NETWORK)
